{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #重排链表"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #stack #recursion #linked-list #two-pointers"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #栈 #递归 #链表 #双指针"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: reorderList"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #重排链表"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个单链表 <code>L</code><em> </em>的头节点 <code>head</code> ，单链表 <code>L</code> 表示为：</p>\n",
    "\n",
    "<p><code>&nbsp;L<sub>0&nbsp;</sub>&rarr; L<sub>1&nbsp;</sub>&rarr; &hellip; &rarr; L<sub>n-1&nbsp;</sub>&rarr; L<sub>n&nbsp;</sub></code><br />\n",
    "请将其重新排列后变为：</p>\n",
    "\n",
    "<p><code>L<sub>0&nbsp;</sub>&rarr;&nbsp;L<sub>n&nbsp;</sub>&rarr;&nbsp;L<sub>1&nbsp;</sub>&rarr;&nbsp;L<sub>n-1&nbsp;</sub>&rarr;&nbsp;L<sub>2&nbsp;</sub>&rarr;&nbsp;L<sub>n-2&nbsp;</sub>&rarr; &hellip;</code></p>\n",
    "\n",
    "<p>不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://pic.leetcode-cn.com/1626420311-PkUiGI-image.png\" style=\"width: 240px; \" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入: </strong>head = [1,2,3,4]\n",
    "<strong>输出: </strong>[1,4,2,3]</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://pic.leetcode-cn.com/1626420320-YUiulT-image.png\" style=\"width: 320px; \" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入: </strong>head = [1,2,3,4,5]\n",
    "<strong>输出: </strong>[1,5,2,4,3]</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>链表的长度范围为 <code>[1, 5 * 10<sup>4</sup>]</code></li>\n",
    "\t<li><code>1 &lt;= node.val &lt;= 1000</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><meta charset=\"UTF-8\" />注意：本题与主站 143&nbsp;题相同：<a href=\"https://leetcode-cn.com/problems/reorder-list/\">https://leetcode-cn.com/problems/reorder-list/</a>&nbsp;</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [LGjMqU](https://leetcode.cn/problems/LGjMqU/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [LGjMqU](https://leetcode.cn/problems/LGjMqU/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def reorderList(self, head: ListNode) -> None:\n",
    "        if head == None:\n",
    "            return\n",
    "        arr, cur = [], head\n",
    "        while cur:\n",
    "            arr.append(cur)\n",
    "            cur = cur.next\n",
    "        i, j = 0, len(arr)-1\n",
    "        while i < j:\n",
    "            next = arr[i].next\n",
    "            arr[i].next = arr[j]\n",
    "            arr[j].next = next\n",
    "            i, j = i+1, j-1\n",
    "        arr[i].next = None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reorderList(self, head: ListNode) -> None:\n",
    "        if not head or not head.next:\n",
    "            return\n",
    "\n",
    "        list_nodes = []\n",
    "        while head:\n",
    "            list_nodes.append(head)\n",
    "            head = head.next\n",
    "\n",
    "        left, right = 0, len(list_nodes) - 1\n",
    "        while left < right:\n",
    "            list_nodes[left].next = list_nodes[right]\n",
    "            list_nodes[right].next = list_nodes[left + 1]\n",
    "            left += 1\n",
    "            right -= 1\n",
    "\n",
    "        list_nodes[left].next = None\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reorderList(self, head: ListNode) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify head in-place instead.\n",
    "        \"\"\"\n",
    "        if not head: return head\n",
    "        mid = self.find_mid(head)\n",
    "        left, right = head, mid.next\n",
    "        mid.next = None\n",
    "        right = self.reverse(right)\n",
    "        self.merge(left, right)\n",
    "    \n",
    "    def merge(self, left, right):\n",
    "        while left and right:\n",
    "            nxt1 = left.next\n",
    "            nxt2 = right.next\n",
    "            left.next = right\n",
    "            left = nxt1\n",
    "            right.next = left\n",
    "            right = nxt2\n",
    "        \n",
    "\n",
    "    def reverse(self, head):\n",
    "        if not head: return head\n",
    "        pre = None\n",
    "        cur = head\n",
    "        while cur:\n",
    "            nxt =  cur.next\n",
    "            cur.next = pre\n",
    "            pre =cur\n",
    "            cur = nxt\n",
    "        return pre\n",
    "\n",
    "    def find_mid(self, head):\n",
    "        if not head: return head\n",
    "        slow, fast = head, head\n",
    "        while fast.next and fast.next.next:\n",
    "            slow = slow.next\n",
    "            fast = fast.next.next\n",
    "        \n",
    "        return slow\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "    #     if not head: return head\n",
    "    #     mid = self.find_mid(head)\n",
    "    #     left, right = head, mid.next\n",
    "    #     mid.next = None\n",
    "    #     right = self.reverse(right)\n",
    "    #     self.merge(left, right)\n",
    "    \n",
    "    # def merge(self, head1, head2):\n",
    "    #     while head1 and head2:\n",
    "    #         next1 = head1.next\n",
    "    #         next2 = head2.next\n",
    "    #         head1.next = head2\n",
    "    #         head1 = next1\n",
    "    #         head2.next = head1\n",
    "    #         head2 = next2\n",
    "\n",
    "\n",
    "    # def reverse(self, head):\n",
    "    #     pre = None\n",
    "    #     cur = head\n",
    "    #     while cur:\n",
    "    #         next = cur.next\n",
    "    #         cur.next = pre\n",
    "    #         pre = cur\n",
    "    #         cur = next\n",
    "        \n",
    "    #     return pre\n",
    "\n",
    "    # def find_mid(self, head):\n",
    "    #     if not head: return head\n",
    "    #     slow, fast = head, head\n",
    "    #     while fast.next and fast.next.next:\n",
    "    #         slow = slow.next\n",
    "    #         fast = fast.next.next\n",
    "        \n",
    "    #     return slow\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reorderList(self, head: ListNode) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify head in-place instead.\n",
    "        \"\"\"\n",
    "        # 思路：反转后半部分链表，然后按次序连接\n",
    "        def find_half(head: ListNode) -> ListNode:\n",
    "            slow = head\n",
    "            fast = head\n",
    "            while fast and fast.next:\n",
    "                slow = slow.next\n",
    "                fast = fast.next.next\n",
    "            return slow\n",
    "        # 反转链表，如果只有一个节点反转完不变\n",
    "        def reverse_listNode(head: ListNode) -> ListNode:\n",
    "            pre = None\n",
    "            while head:\n",
    "                next_node = head.next\n",
    "                head.next = pre\n",
    "                pre = head\n",
    "                head = next_node\n",
    "            return pre\n",
    "        \n",
    "        if head.next is None or head.next.next is None:\n",
    "            return\n",
    "        node = find_half(head)\n",
    "        # 断开成两个链表\n",
    "        pre = None\n",
    "        cur = head\n",
    "        while cur != node:\n",
    "            pre = cur\n",
    "            cur = cur.next\n",
    "        pre.next = None\n",
    "        # 反转链表\n",
    "        head2 = reverse_listNode(node)\n",
    "\n",
    "        while head2 and head:\n",
    "            next_node1 = head.next\n",
    "            head.next = head2\n",
    "            next_node2 = head2.next\n",
    "            if next_node1 is not None:\n",
    "                head2.next = next_node1\n",
    "            head = next_node1\n",
    "            head2 = next_node2\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reorderList(self, head: ListNode) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify head in-place instead.\n",
    "        \"\"\"\n",
    "        # 思路：反转后半部分链表，然后按次序连接\n",
    "        def find_half(head: ListNode) -> ListNode:\n",
    "            slow = head\n",
    "            fast = head\n",
    "            while fast and fast.next:\n",
    "                slow = slow.next\n",
    "                fast = fast.next.next\n",
    "            return slow\n",
    "        # 反转链表，如果只有一个节点反转完不变\n",
    "        def reverse_listNode(head: ListNode) -> ListNode:\n",
    "            pre = None\n",
    "            while head:\n",
    "                next_node = head.next\n",
    "                head.next = pre\n",
    "                pre = head\n",
    "                head = next_node\n",
    "            return pre\n",
    "        \n",
    "        if head.next is None or head.next.next is None:\n",
    "            return\n",
    "        node = find_half(head)\n",
    "        # 断开成两个链表\n",
    "        pre = None\n",
    "        cur = head\n",
    "        while cur != node:\n",
    "            pre = cur\n",
    "            cur = cur.next\n",
    "        pre.next = None\n",
    "        # 反转链表\n",
    "        head2 = reverse_listNode(node)\n",
    "        print(node.val, head2.val)\n",
    "        while head2 and head:\n",
    "            print(head.val, head2.val)\n",
    "            next_node1 = head.next\n",
    "            head.next = head2\n",
    "            next_node2 = head2.next\n",
    "            if next_node1 is not None:\n",
    "                head2.next = next_node1\n",
    "            head = next_node1\n",
    "            head2 = next_node2\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reorderList(self, head: ListNode) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify head in-place instead.\n",
    "        \"\"\"\n",
    "        tmp = []\n",
    "        p = head\n",
    "        newhead = ListNode(-1)\n",
    "        q = newhead\n",
    "        count = 1\n",
    "        while p:\n",
    "            tmp.append(p)\n",
    "            p = p.next\n",
    "        i = 0\n",
    "        j = len(tmp) - 1\n",
    "        while i <= j:\n",
    "            if count % 2 != 0:\n",
    "                print(tmp[i].val)\n",
    "                q.next = tmp[i]\n",
    "                i += 1\n",
    "            else:\n",
    "                print(tmp[j].val)\n",
    "                q.next = tmp[j]\n",
    "                j -= 1\n",
    "            count += 1\n",
    "            q = q.next\n",
    "        q.next = None\n",
    "        return newhead.next\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reorderList(self, head: ListNode) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify head in-place instead.\n",
    "        \"\"\"\n",
    "        if not head:    return head\n",
    "        \n",
    "        buf = []\n",
    "        point = head\n",
    "        while point:\n",
    "            buf.append([point.val, point])\n",
    "            point = point.next\n",
    "        \n",
    "        buf[len(buf)//2][1].next = None\n",
    "        cur = ListNode()\n",
    "        final = cur\n",
    "        l, r = 0, len(buf)-1\n",
    "        while l < r:\n",
    "            cur.next = buf[l][1]\n",
    "            cur = cur.next\n",
    "            cur.next = buf[r][1]\n",
    "            cur = cur.next\n",
    "            l += 1\n",
    "            r -= 1\n",
    "        \n",
    "        if l == r:\n",
    "            cur.next = buf[l][1]\n",
    "            cur = cur.next\n",
    "\n",
    "        return final.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reorderList(self, head: ListNode) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify head in-place instead.\n",
    "        \"\"\"\n",
    "        l = 0       # 记录链表的长度，结点交换操作需要进行l//2次\n",
    "        nodes = []\n",
    "        tmp = head\n",
    "        while tmp:\n",
    "            l += 1\n",
    "            nodes.append(tmp.val)\n",
    "            tmp = tmp.next\n",
    "        tmp = head; pre = ListNode(0); pre.next = head\n",
    "        for i in range(l//2):\n",
    "            a = tmp.next                        \n",
    "            tmp.next = ListNode(nodes.pop())\n",
    "            tmp = tmp.next\n",
    "            tmp.next = a\n",
    "            pre = tmp\n",
    "            tmp = tmp.next\n",
    "        if l % 2 == 0:\n",
    "            pre.next = None\n",
    "        else:\n",
    "            pre.next.next = None\n",
    "\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reorderList(self, head: ListNode) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify head in-place instead.\n",
    "        \"\"\"\n",
    "        hash_table = dict()\n",
    "        index = 0\n",
    "        while head is not None:\n",
    "            hash_table[index] = head\n",
    "            head = head.next\n",
    "            index += 1\n",
    "\n",
    "        dummy_head = ListNode()\n",
    "        cur = dummy_head\n",
    "        even = 0\n",
    "        odd = index - 1\n",
    "        for i in range(index):\n",
    "            if i % 2 == 0:\n",
    "                cur.next = hash_table[even]\n",
    "                even += 1\n",
    "            else:\n",
    "                cur.next = hash_table[odd]\n",
    "                odd -= 1\n",
    "            cur = cur.next\n",
    "        cur.next = None\n",
    "        return dummy_head.next\n",
    "                \n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# # Definition for singly-linked list.\n",
    "# # class ListNode:\n",
    "# #     def __init__(self, val=0, next=None):\n",
    "# #         self.val = val\n",
    "# #         self.next = next\n",
    "class Solution:\n",
    "    def reorderList(self, head: ListNode) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify head in-place instead.\n",
    "        \"\"\"\n",
    "        if not head:\n",
    "            return \n",
    "\n",
    "        cur = head \n",
    "        hash_table = {}\n",
    "        count = 0\n",
    "        while cur:\n",
    "            hash_table[count] = cur\n",
    "            cur = cur.next\n",
    "            # if count > 0:\n",
    "                # hash_table[count-1].next = None\n",
    "            count += 1\n",
    "        \n",
    "        # cur = dummy\n",
    "        i, j = 0, len(hash_table)-1\n",
    "        while i < j:\n",
    "            hash_table[i].next = hash_table[j]\n",
    "            i += 1\n",
    "            if i == j:\n",
    "                break\n",
    "            hash_table[j].next = hash_table[i]\n",
    "            j -= 1\n",
    "\n",
    "        hash_table[i].next = None\n",
    "        \n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reorderList(self, head: ListNode) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify head in-place instead.\n",
    "        \"\"\"\n",
    "        head_dict = {}\n",
    "        tail = head\n",
    "        i = 1\n",
    "        while tail:\n",
    "            head_dict[i] = tail\n",
    "            i+=1\n",
    "            tail = tail.next\n",
    "        \n",
    "        k,p=2,i-1\n",
    "        j=1\n",
    "        tmp=head\n",
    "        while k<=p:\n",
    "            if j % 2==0:\n",
    "                tmp.next=head_dict[k]\n",
    "                k+=1\n",
    "            else:\n",
    "                tmp.next=head_dict[p]\n",
    "                p-=1\n",
    "            tmp=tmp.next\n",
    "            j+=1\n",
    "        tmp.next=None\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reorderList(self, head: ListNode) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify head in-place instead.\n",
    "        \"\"\"\n",
    "        # def reorder(node):\n",
    "        #     if node.next==None or node.next.next==None:\n",
    "        #         return node\n",
    "        #     else:\n",
    "        #         nextnode=node.next\n",
    "        #         node.next=None\n",
    "        #         checklastnode=nextnode\n",
    "        #         while checklastnode.next.next!=None:\n",
    "        #             checklastnode=checklastnode.next\n",
    "        #         lastnode=checklastnode.next\n",
    "        #         checklastnode.next=None\n",
    "        #         node.next=lastnode\n",
    "        #         lastnode.next=reorder(nextnode)\n",
    "        #         return node\n",
    "        # reorder(head)\n",
    "        rehead=ListNode(0,head)\n",
    "        dic={}\n",
    "        i=0\n",
    "        while head!=None:            \n",
    "            dic[i]=head\n",
    "            head=head.next\n",
    "            dic[i].next=None\n",
    "            i+=1\n",
    "        head=rehead\n",
    "        for j in range(i//2):\n",
    "            head.next=dic[j]\n",
    "            dic[j].next=dic[i-1-j]\n",
    "            head=dic[i-1-j]\n",
    "        if i%2:\n",
    "            pass\n",
    "            head.next=dic[i//2]\n",
    "        return rehead.next\n",
    "            \n",
    "        \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reorderList(self, head: ListNode) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify head in-place instead.\n",
    "        \"\"\"\n",
    "        head_rev = None\n",
    "        temp=head\n",
    "        n = 0\n",
    "        while temp!=None:\n",
    "            n+=1\n",
    "            p=ListNode(temp.val)\n",
    "            p.next=head_rev\n",
    "            head_rev=p\n",
    "            temp=temp.next\n",
    "        #print(n)\n",
    "        #print(head_rev)\n",
    "        \n",
    "        i=1\n",
    "        p_curr=head\n",
    "        while(1):\n",
    "            #print(\"==>\",i,n)\n",
    "            if i>=n:\n",
    "                p_curr.next=None\n",
    "                #print(\"==>end1\")\n",
    "                break\n",
    "            elif i+2<=n:\n",
    "                temp1 = p_curr.next\n",
    "                temp2 = head_rev.next\n",
    "                p_curr.next = head_rev\n",
    "                p_curr=p_curr.next\n",
    "                p_curr.next=temp1\n",
    "                head_rev=temp2\n",
    "                p_curr=p_curr.next\n",
    "            else:\n",
    "                p_curr = p_curr.next\n",
    "                p_curr.next=None\n",
    "                #print(\"==>end2\")\n",
    "                break\n",
    "\n",
    "            i+=2\n",
    "            #print(head)\n",
    "            #print(head_rev)\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reorderList(self, head: ListNode) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify head in-place instead.\n",
    "        \"\"\"\n",
    "        cur = head\n",
    "        value, n = {}, 0\n",
    "        while cur:\n",
    "            value[n] = cur\n",
    "            n += 1\n",
    "            cur = cur.next\n",
    "        cur = head\n",
    "        now, left, right = 0, 0, n-1\n",
    "        while now < n:\n",
    "\n",
    "            if now % 2 != 0:\n",
    "                cur.next = value[right]\n",
    "                right -= 1\n",
    "            else:\n",
    "                cur.next = value[left]\n",
    "                left += 1\n",
    "            cur = cur.next\n",
    "            now += 1\n",
    "        cur.next = None\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reorderList(self, head: ListNode) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify head in-place instead.\n",
    "        \"\"\"\n",
    "        if head is None:return head\n",
    "        mid,n=self.findmid(head)\n",
    "        l2=self.reverse(head)\n",
    "        p1=head\n",
    "        p2=l2\n",
    "        t1=head\n",
    "        t2=ListNode(p2.val,None)\n",
    "        while t1!=mid:\n",
    "            t1=t1.next\n",
    "            p1.next=t2\n",
    "            p1.next.next=t1\n",
    "            p1=p1.next.next\n",
    "            p2=p2.next\n",
    "            t2=ListNode(p2.val,None)\n",
    "            n-=2\n",
    "        while n-1>0:\n",
    "            p1=p1.next\n",
    "            n-=1\n",
    "        p1.next=None\n",
    "        \n",
    "    def reverse(self,head):\n",
    "        newhead=ListNode(head.val,None)\n",
    "        p=head.next\n",
    "        while p!=None:\n",
    "            t=ListNode(p.val,newhead)\n",
    "            newhead=t\n",
    "            p=p.next\n",
    "        return newhead\n",
    "\n",
    "\n",
    "    def findmid(self,head):\n",
    "        if head == None: return head\n",
    "        n=1\n",
    "        p1=head\n",
    "        while p1.next!=None:\n",
    "            n+=1\n",
    "            p1=p1.next\n",
    "        l=math.ceil(n/2)\n",
    "        p2=head\n",
    "        l-=1\n",
    "        while l>0:\n",
    "            p2=p2.next\n",
    "            l-=1\n",
    "        return p2,n\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reorderList(self, head: ListNode) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify head in-place instead.\n",
    "        \"\"\"\n",
    "        new = ListNode(0)\n",
    "        p = head\n",
    "        n = 0\n",
    "        while p:\n",
    "            n += 1\n",
    "            q = ListNode(p.val)\n",
    "            q.next = new.next\n",
    "            new.next = q\n",
    "            p = p.next\n",
    "        \n",
    "        l = head\n",
    "        r = new.next\n",
    "        for i in range(n//2):\n",
    "            temp = ListNode(r.val)\n",
    "            temp.next = l.next\n",
    "            l.next = temp\n",
    "            l = temp.next\n",
    "            r = r.next\n",
    "        if n % 2 == 0:\n",
    "            temp.next = None\n",
    "        else:\n",
    "            l.next = None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reorderList(self, head: ListNode) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify head in-place instead.\n",
    "        \"\"\"\n",
    "        def reverse(root):\n",
    "            head = ListNode(0)\n",
    "            while(root):\n",
    "                #root_copy = root\n",
    "                \n",
    "                node = ListNode(0)\n",
    "                node.val = root.val\n",
    "                root = root.next\n",
    "                node.next = head.next\n",
    "                head.next = node\n",
    "            return head.next\n",
    "        head1_copy = head\n",
    "        head2 = reverse(head)\n",
    "        # while(head):\n",
    "        #     print(\"head1\",head.val)\n",
    "        #     head = head.next\n",
    "        res = result = ListNode(0)\n",
    "        lenth = 0\n",
    "        while(head1_copy):\n",
    "            lenth+=1\n",
    "            head1_copy = head1_copy.next\n",
    "        head1_copy = head\n",
    "        count = 0\n",
    "        print(\"len\",lenth)\n",
    "        while(head1_copy and head2 and count <= lenth-1):\n",
    "            if count %2 == 0:\n",
    "                result.next = head1_copy\n",
    "                result = result.next\n",
    "                head1_copy = head1_copy.next\n",
    "                #print(result.val)\n",
    "                #print(head1_copy.val)\n",
    "                count += 1\n",
    "            else:\n",
    "                result.next = head2\n",
    "                result = result.next\n",
    "                head2 = head2.next\n",
    "                #print(result.val)\n",
    "                count += 1\n",
    "        result.next = None\n",
    "        return res.next\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reorderList(self, head: ListNode) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify head in-place instead.\n",
    "        \"\"\"\n",
    "\n",
    "        count = 0\n",
    "        dummy = ListNode(-1)\n",
    "        dummy.next = head\n",
    "        cur = head \n",
    "        hash_table = {}\n",
    "        while cur:\n",
    "            hash_table[count] = cur\n",
    "            cur = cur.next\n",
    "            if count > 0:\n",
    "                hash_table[count-1].next = None\n",
    "            count += 1\n",
    "        \n",
    "        cur = dummy\n",
    "        i, j = 0, len(hash_table)-1\n",
    "        while i < j:\n",
    "            hash_table[i].next = hash_table[j]\n",
    "            i += 1\n",
    "            if i >= j:\n",
    "                break\n",
    "            hash_table[j].next = hash_table[i]\n",
    "            j -= 1\n",
    "\n",
    "\n",
    "        return dummy.next\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reorderList(self, head: ListNode) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify head in-place instead.\n",
    "        \"\"\"\n",
    "        p = head\n",
    "        l = []\n",
    "        while p:\n",
    "            l.append(p.val)\n",
    "            p = p.next\n",
    "        n = len(l)\n",
    "        p = head\n",
    "        h = head\n",
    "        while p.next:\n",
    "            q = p.next\n",
    "            t = ListNode(l[-1])\n",
    "            t.next = None\n",
    "            l.pop()\n",
    "            if q.next:\n",
    "                t.next = q\n",
    "                p.next = t\n",
    "                p = q\n",
    "            else:\n",
    "                break\n",
    "        #按原链表长度做截取\n",
    "        lenth_list = 1\n",
    "        p = h\n",
    "        while lenth_list<n:\n",
    "            p = p.next\n",
    "            lenth_list+=1\n",
    "        p.next = None\n",
    "        return h"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reorderList(self, head: ListNode) -> None:\n",
    "        cur=head\n",
    "        temp=[]\n",
    "        \n",
    "        while cur:\n",
    "            temp.append(cur.val)\n",
    "            cur=cur.next\n",
    "        nus=len(temp)\n",
    "        cur=head\n",
    "        while cur:\n",
    "            nextNode=cur.next\n",
    "            node=ListNode(temp.pop())\n",
    "            cur.next=node\n",
    "            node.next=nextNode\n",
    "            cur=nextNode\n",
    "        cur=head\n",
    "        for i in range(nus-1):\n",
    "            cur=cur.next\n",
    "        cur.next=None\n",
    "        return head\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reorderList(self, head: ListNode) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify head in-place instead.\n",
    "        \"\"\"\n",
    "\n",
    "        count = 0\n",
    "        dummy = ListNode(-1)\n",
    "        dummy.next = head\n",
    "        cur = head \n",
    "        hash_table = {}\n",
    "        while cur:\n",
    "            hash_table[count] = cur\n",
    "            cur = cur.next\n",
    "            if count > 0:\n",
    "                hash_table[count-1].next = None\n",
    "            count += 1\n",
    "        \n",
    "        cur = dummy\n",
    "        print(hash_table)\n",
    "        i, j = 0, len(hash_table)-1\n",
    "        print(j)\n",
    "        while i < j:\n",
    "            hash_table[i].next = hash_table[j]\n",
    "            i += 1\n",
    "            if i >= j:\n",
    "                break\n",
    "            hash_table[j].next = hash_table[i]\n",
    "            j -= 1\n",
    "\n",
    "\n",
    "        return dummy.next\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reorderList(self, head: ListNode) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify head in-place instead.\n",
    "        \"\"\"\n",
    "        curr1 = head\n",
    "        new_head = ListNode(curr1.val)\n",
    "        curr2 = new_head\n",
    "        leng = 0\n",
    "        while curr1:\n",
    "            leng += 1\n",
    "            curr1 = curr1.next\n",
    "            if curr1:\n",
    "                curr2.next = ListNode(curr1.val)\n",
    "                curr2 = curr2.next\n",
    "        rvs_new_head = None\n",
    "        curr3 = new_head\n",
    "        while curr3:\n",
    "            curr3_next = curr3.next\n",
    "            curr3.next = rvs_new_head\n",
    "            rvs_new_head = curr3\n",
    "            curr3 = curr3_next\n",
    "        curr4 = head\n",
    "        curr5 = rvs_new_head\n",
    "        count = 0\n",
    "        result=[]\n",
    "        while count < int(leng/2):\n",
    "            result.append(curr4.val)\n",
    "            result.append(curr5.val)\n",
    "            count += 1\n",
    "            curr4 = curr4.next\n",
    "            curr5 = curr5.next\n",
    "        if leng%2==1:\n",
    "            result.append(curr4.val)\n",
    "        head2 = ListNode(result[0])\n",
    "        curr6 = head2\n",
    "        for i in range(1,len(result)):\n",
    "            curr6.next = ListNode(result[i])\n",
    "            curr6 = curr6.next\n",
    "        head.next = head2\n",
    "        head.next = head.next.next\n",
    "            \n",
    "        \n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reorderList(self, head: ListNode) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify head in-place instead.\n",
    "        \"\"\"\n",
    "        curr1 = head\n",
    "        new_head = ListNode(curr1.val)\n",
    "        #复制链\n",
    "        curr2 = new_head\n",
    "        leng = 0\n",
    "        while curr1:\n",
    "            leng += 1\n",
    "            curr1 = curr1.next\n",
    "            if curr1:\n",
    "                curr2.next = ListNode(curr1.val)\n",
    "                curr2 = curr2.next\n",
    "        #逆链\n",
    "        rvs_new_head = None\n",
    "        curr3 = new_head\n",
    "        while curr3:\n",
    "            curr3_next = curr3.next\n",
    "            curr3.next = rvs_new_head\n",
    "            rvs_new_head = curr3\n",
    "            curr3 = curr3_next\n",
    "        #原链和逆链重新拉到头\n",
    "        curr4 = head\n",
    "        curr5 = rvs_new_head\n",
    "        count = 0\n",
    "        #存值\n",
    "        result=[]\n",
    "        while count < int(leng/2):\n",
    "            result.append(curr4.val)\n",
    "            result.append(curr5.val)\n",
    "            count += 1\n",
    "            curr4 = curr4.next\n",
    "            curr5 = curr5.next\n",
    "        #奇长度\n",
    "        if leng%2==1:\n",
    "            result.append(curr4.val)\n",
    "        head2 = ListNode(result[0])\n",
    "        curr6 = head2\n",
    "        for i in range(1,len(result)):\n",
    "            curr6.next = ListNode(result[i])\n",
    "            curr6 = curr6.next\n",
    "        head.next = head2\n",
    "        #去除第二个node\n",
    "        head.next = head.next.next\n",
    "            \n",
    "        \n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reorderList(self, head):\n",
    "        if not head:\n",
    "            return head\n",
    "        mid = self.mid(head)\n",
    "        l1 = head\n",
    "        l2 = mid.next\n",
    "        mid.next = None\n",
    "        l2 = self.reverseList(l2)\n",
    "        self.mergeLists(l1, l2)\n",
    "        \n",
    "    \n",
    "    def mid(self, head):\n",
    "        slow = fast = head\n",
    "        while fast.next and fast.next.next:\n",
    "            slow = slow.next\n",
    "            fast = fast.next.next\n",
    "        return slow\n",
    "        \n",
    "    def reverseList(self, head):\n",
    "        if not head or not head.next:\n",
    "            return head\n",
    "        last = self.reverseList(head.next)\n",
    "        head.next.next = head\n",
    "        head.next = None\n",
    "        return last\n",
    "        \n",
    "    def mergeLists(self, p, q):\n",
    "        while p and q:\n",
    "            p1 = p.next\n",
    "            q1 = q.next\n",
    "            p.next = q\n",
    "            p = p1\n",
    "            q.next = p\n",
    "            q = q1\n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reorderList(self, head: ListNode) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify head in-place instead.\n",
    "        \"\"\"\n",
    "        ########################################\n",
    "        # 1. 找到中间节点（快慢指针）\n",
    "        # 2. 反转链表后半部分\n",
    "        # 3. 合并两个链表\n",
    "        ########################################\n",
    "        if head is None or head.next is None:\n",
    "            return head\n",
    "        pre = None\n",
    "        slow = head\n",
    "        fast = head.next\n",
    "        while fast is not None:\n",
    "            pre = slow\n",
    "            slow = slow.next\n",
    "            fast = fast.next\n",
    "            if fast is None:\n",
    "                break\n",
    "            fast = fast.next\n",
    "        pre.next = None\n",
    "        slow = self.reverseList(slow)\n",
    "\n",
    "        p = head\n",
    "        while slow is not None:\n",
    "            tmp = slow\n",
    "            if p.next is None:\n",
    "                p.next = slow\n",
    "                break\n",
    "            else:\n",
    "                slow = slow.next\n",
    "                tmp.next = p.next\n",
    "                p.next = tmp\n",
    "                p = p.next.next\n",
    "\n",
    "    def reverseList(self, head):\n",
    "        if head is None or head.next is None:\n",
    "            return head\n",
    "        new_head = self.reverseList(head.next)\n",
    "        head.next.next = head\n",
    "        head.next = None\n",
    "        return new_head\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reorderList(self, head: ListNode) -> None:\n",
    "        if not head: return head\n",
    "        slow = fast = head\n",
    "        while fast and fast.next:\n",
    "            slow = slow.next\n",
    "            fast = fast.next.next\n",
    "        gap = slow\n",
    "        p = slow.next\n",
    "        slow.next = None\n",
    "        while p:\n",
    "            tmp = p.next\n",
    "            p.next = slow\n",
    "            slow = p \n",
    "            p = tmp\n",
    "        merge(head, slow, gap)\n",
    "\n",
    "def merge(x, y, gap):\n",
    "    if x == gap:\n",
    "        x.next = None\n",
    "        return\n",
    "    if not y: return\n",
    "    xn = x.next\n",
    "    yn = y.next\n",
    "    x.next = y\n",
    "    y.next = xn\n",
    "    merge(xn, yn, gap)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reorderList(self, head: ListNode) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify head in-place instead.\n",
    "        \"\"\"\n",
    "        if head is None:\n",
    "            return None\n",
    "        def revserse(head:ListNode):\n",
    "            if head is None or head.next is None:\n",
    "                return head\n",
    "            last = revserse(head.next)\n",
    "            head.next.next = head\n",
    "            head.next = None\n",
    "            return last\n",
    "        slow,fast = head,head\n",
    "        while fast is not None and fast.next is not None:\n",
    "            slow = slow.next\n",
    "            fast = fast.next.next\n",
    "        link1 = head\n",
    "        link2 = slow.next\n",
    "        slow.next = None\n",
    "        link2 = revserse(link2)\n",
    "\n",
    "        while link2:\n",
    "            nxt2 = link2.next\n",
    "            nxt1 = link1.next\n",
    "            link2.next = link1.next\n",
    "            link1.next = link2\n",
    "            link1 = nxt1\n",
    "            link2 = nxt2\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reorderList(self, head: ListNode) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify head in-place instead.\n",
    "        \"\"\"\n",
    "        # 找中点\n",
    "        def findMiddle(head):\n",
    "            fast,slow = head,head\n",
    "            while(fast.next and fast.next.next):\n",
    "                fast = fast.next.next\n",
    "                slow = slow.next\n",
    "            return slow\n",
    "        # 反转链表\n",
    "        def reverse(head):\n",
    "            if(not head or not head.next):\n",
    "                return head\n",
    "            new = reverse(head.next)\n",
    "            head.next.next = head\n",
    "            head.next = None\n",
    "            return new\n",
    "        # 合并链表，l2合并到l1中\n",
    "        def merge(l1,l2):\n",
    "            cur1,cur2 = l1,l2\n",
    "            while(cur1 and cur2):\n",
    "                temp1 = cur1.next\n",
    "                temp2 = cur2.next\n",
    "                cur1.next = cur2\n",
    "                cur2.next = temp1\n",
    "                cur1 = temp1\n",
    "                cur2 = temp2\n",
    "        mid = findMiddle(head)\n",
    "        r_v = reverse(mid)\n",
    "        merge(head,r_v)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reorderList(self, head: ListNode) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify head in-place instead.\n",
    "        \"\"\"\n",
    "\n",
    "        def reverse(head):\n",
    "            if(not head or not head.next):\n",
    "                return head\n",
    "            new = reverse(head.next)\n",
    "            head.next.next = head\n",
    "            head.next = None\n",
    "            return new\n",
    "        # 找中点,slow\n",
    "        slow,fast = head,head\n",
    "        pre = None\n",
    "        while(fast and fast.next):\n",
    "            pre = slow\n",
    "            slow = slow.next\n",
    "            fast = fast.next.next\n",
    "        if(pre):\n",
    "            pre.next = None\n",
    "            after = reverse(slow)\n",
    "            cur = head\n",
    "            while(cur.next and after.next):\n",
    "                temp1 = cur.next\n",
    "                temp2 = after.next\n",
    "                cur.next = after\n",
    "                cur.next.next = temp1\n",
    "                after = temp2\n",
    "                cur = temp1\n",
    "            if(after):\n",
    "                cur.next = after\n",
    "\n",
    "\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reverse(self, head: ListNode) -> ListNode:\n",
    "        if not head or not head.next:\n",
    "            return head\n",
    "        last = self.reverse(head.next)\n",
    "        head.next.next = head\n",
    "        head.next = None\n",
    "        return last\n",
    "\n",
    "    def reorderList(self, head: ListNode) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify head in-place instead.\n",
    "        \"\"\"            \n",
    "        slow = head\n",
    "        fast = head.next\n",
    "        while fast and fast.next:\n",
    "            slow = slow.next\n",
    "            fast = fast.next.next\n",
    "\n",
    "        mid = slow.next\n",
    "        mid = self.reverse(mid)\n",
    "        # print(mid)\n",
    "\n",
    "        left = head\n",
    "        right = mid\n",
    "        while left:\n",
    "            tmp = left.next\n",
    "            left.next = right\n",
    "            left = right\n",
    "            right = tmp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reorderList(self, head: ListNode) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify head in-place instead.\n",
    "        \"\"\"\n",
    "        slow, fast = head, head\n",
    "        while 1:\n",
    "            if fast.next is None or fast.next.next is None: break\n",
    "            slow = slow.next\n",
    "            fast = fast.next.next     \n",
    "            \n",
    "        latter_head = self.flip(slow.next)\n",
    "        slow.next = None\n",
    "        \n",
    "        former_head = head\n",
    "        \n",
    "        while latter_head:\n",
    "            tmp = latter_head.next\n",
    "            #print(latter_head.val)\n",
    "            latter_head.next = former_head.next\n",
    "            former_head.next = latter_head\n",
    "            latter_head = tmp\n",
    "            former_head = former_head.next.next\n",
    "            #print(latter_head.val)\n",
    "        return\n",
    "        \n",
    "    def flip(self, head):\n",
    "        if not head:\n",
    "            return None\n",
    "        if not head.next:\n",
    "            return head\n",
    "        headNode = self.flip(head.next)\n",
    "        head.next.next = head\n",
    "        head.next = None\n",
    "        return headNode"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reorderList(self, head: ListNode) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify head in-place instead.\n",
    "        \"\"\"\n",
    "        def reverse(head):\n",
    "            if not head:\n",
    "                return head\n",
    "            if not head.next:\n",
    "                return head\n",
    "            first = reverse(head.next)\n",
    "            head.next.next = head\n",
    "            head.next = None\n",
    "            return first\n",
    "        def get_middle(head):\n",
    "            fast = head\n",
    "            slow = head\n",
    "            while fast.next and fast.next.next:\n",
    "                fast = fast.next.next\n",
    "                slow = slow.next\n",
    "            #1  2 3 4 \n",
    "            #   s  f\n",
    "            return slow\n",
    "        def merge(first, last):\n",
    "            while first and last:\n",
    "                nxt1 = first.next\n",
    "                nxt2 = last.next\n",
    "                first.next = last\n",
    "                first = nxt1\n",
    "                last.next = first\n",
    "                last = nxt2\n",
    "\n",
    "        mid = get_middle(head)\n",
    "        last_list = mid.next\n",
    "        mid.next = None\n",
    "        last_list = reverse(last_list)\n",
    "        merge(head, last_list)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reorderList(self, head: ListNode) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify head in-place instead.\n",
    "        \"\"\"\n",
    "        # 首先需要找到中间节点，之后将链表反转，最后进行合并\n",
    "        def find_mid(node: ListNode):\n",
    "            if node is None or node.next is None:\n",
    "                return node\n",
    "            vir = ListNode(-1)\n",
    "            vir.next = node\n",
    "            left = vir\n",
    "            right = vir\n",
    "            while right is not None and right.next is not None:\n",
    "                left = left.next\n",
    "                right = right.next.next\n",
    "            return left\n",
    "\n",
    "        def reverse(node: ListNode):\n",
    "            if node is None or node.next is None:\n",
    "                return node\n",
    "            new_node = reverse(node.next)\n",
    "            node.next.next = node\n",
    "            node.next = None\n",
    "            return new_node\n",
    "\n",
    "        def merge(head):\n",
    "            left = find_mid(head)\n",
    "            l1 = head\n",
    "            l2 = left.next\n",
    "            left.next = None\n",
    "            l2 = reverse(l2)\n",
    "            while l1 and l2:\n",
    "                tmp1 = l1.next\n",
    "                tmp2 = l2.next\n",
    "                l1.next = l2\n",
    "                l1 = tmp1\n",
    "                l2.next = l1\n",
    "                l2 = tmp2\n",
    "        merge(head)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reorderList(self, head: ListNode) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify head in-place instead.\n",
    "        \"\"\"\n",
    "        p1=p2=head\n",
    "        while p2 is not None and p2.next is not None:\n",
    "            p1=p1.next\n",
    "            p2=p2.next.next\n",
    "        t=p1.next\n",
    "        p1.next=None\n",
    "        def revList(head):\n",
    "            if head is None or head.next is None:\n",
    "                return head\n",
    "            t = revList(head.next)\n",
    "            head.next.next=head\n",
    "            head.next = None\n",
    "            return t\n",
    "        p2=revList(t)\n",
    "        p1=head\n",
    "        while p1 is not None and p2 is not None:\n",
    "            t1,t2=p1.next,p2.next\n",
    "            p1.next,p2.next=p2,t1\n",
    "            p1,p2=t1,t2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reorderList(self, head: ListNode) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify head in-place instead.\n",
    "        \"\"\"\n",
    "        m=self.mid(head)\n",
    "        r=self.reverse(m.next)\n",
    "        m.next=None\n",
    "        head=self.merge(head,r)\n",
    "\n",
    "    def mid(self,head):\n",
    "        l,f=head,head\n",
    "        while f.next and f.next.next:\n",
    "            l=l.next\n",
    "            f=f.next.next\n",
    "        return l\n",
    "\n",
    "\n",
    "    def reverse(self,head):\n",
    "        if not head or not head.next:\n",
    "            return head\n",
    "        p=self.reverse(head.next)\n",
    "        head.next.next=head\n",
    "        head.next=None\n",
    "        return p\n",
    "\n",
    "    def merge(self,x,y):\n",
    "        \n",
    "        dummy=ListNode()\n",
    "        p=dummy\n",
    "        while x and y:\n",
    "            p.next=x\n",
    "            p=p.next\n",
    "            x=x.next\n",
    "            p.next=y\n",
    "            p=p.next\n",
    "            y=y.next\n",
    "        if x:\n",
    "            p.next=x\n",
    "        if y:\n",
    "            p.next=y\n",
    "        return dummy.next\n",
    "        \n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reorderList(self, head: ListNode) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify head in-place instead.\n",
    "        \"\"\"\n",
    "        cnt,cur = 0,head\n",
    "        while cur:\n",
    "            cnt += 1\n",
    "            cur = cur.next\n",
    "        return self.recur(head, cnt)\n",
    "        \n",
    "    def recur(self, head, length):\n",
    "        if length == 1:\n",
    "            out_tail = head.next\n",
    "            head.next = None\n",
    "            return out_tail\n",
    "        if length == 2:\n",
    "            out_tail = head.next.next\n",
    "            head.next.next = None\n",
    "            return out_tail\n",
    "        tail = self.recur(head.next, length-2)\n",
    "        sub_head = head.next\n",
    "        out_tail = tail.next\n",
    "        head.next = tail\n",
    "        tail.next = sub_head\n",
    "        return out_tail"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reverse(self, head):\n",
    "        if not head.next:\n",
    "            return head\n",
    "        head2 = self.reverse(head.next)\n",
    "        head.next.next = head\n",
    "        head.next = None\n",
    "        return head2\n",
    "\n",
    "    def reorderList(self, head: ListNode) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify head in-place instead.\n",
    "        \"\"\"\n",
    "        slow, fast = head, head.next\n",
    "        while fast and fast.next:\n",
    "            slow = slow.next\n",
    "            fast = fast.next.next\n",
    "        l2 = slow.next\n",
    "        if not l2:\n",
    "            return\n",
    "        slow.next = None\n",
    "        l2,slow = self.reverse(l2),head\n",
    "        while l2:\n",
    "            next_node = slow.next\n",
    "            l2_next = l2.next\n",
    "\n",
    "            slow.next = l2\n",
    "            slow.next.next = next_node\n",
    "            slow = slow.next.next\n",
    "            l2 = l2_next\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def helper(self, head, stack, ind):\n",
    "        # print('head:', head)\n",
    "        # 每次缩减左右结点，然后指向内部区间的结点排序后的结果就行了\n",
    "        if not head or not head.next or not head.next.next:\n",
    "            return head\n",
    "\n",
    "        # 不能连续弹出两个结点，只能弹出一个，之前死循环是因为连续弹出两个右端点导致的\n",
    "        tail = stack.pop(-1)\n",
    "        pre = stack[-1]\n",
    "        # print('pre:', pre)\n",
    "        # print('tail:', tail)\n",
    "        # pre = head\n",
    "        # # 找到倒数第二个节点\n",
    "        # while pre.next and pre.next.next:\n",
    "        #     pre = pre.next\n",
    "\n",
    "        # 下一个区间的链表        \n",
    "        next_list = head.next\n",
    "        # 将新区间的尾节点next置为空\n",
    "        pre.next = None\n",
    "        # 将当前区间左端点的next置为尾节点\n",
    "        head.next = tail \n",
    "        # 尾节点的next为新区间处理结果的头节点\n",
    "        tail.next = self.helper(next_list, stack, ind - 1)\n",
    "        return head\n",
    "\n",
    "    def reorderList(self, head: ListNode) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify head in-place instead.\n",
    "        \"\"\"\n",
    "        stack = []\n",
    "        cur = head\n",
    "        while cur:\n",
    "            stack.append(cur)\n",
    "            cur = cur.next\n",
    "\n",
    "        cur = head\n",
    "        head = self.helper(cur, stack, len(stack))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "\n",
    "class Solution:\n",
    "    def reorderList(self, head: ListNode) -> None:\n",
    "\n",
    "        \"\"\"\n",
    "        Do not return anything, modify head in-place instead.\n",
    "        \"\"\"\n",
    "\n",
    "        \"\"\"\n",
    "        Do not return anything, modify head in-place instead.\n",
    "        \"\"\"\n",
    "\n",
    "        if head is None or head.next is None or head.next.next is None:\n",
    "            return\n",
    "\n",
    "        N = 0\n",
    "        temp = head\n",
    "        while temp is not None:\n",
    "            N += 1\n",
    "            temp = temp.next\n",
    "\n",
    "        def rc(head: ListNode, n: int):\n",
    "\n",
    "            if n == 1:\n",
    "                tailNode = head.next\n",
    "                head.next = None\n",
    "                return tailNode\n",
    "\n",
    "            elif n == 2:\n",
    "                tailNode = head.next.next\n",
    "                head.next.next = None\n",
    "                return tailNode\n",
    "\n",
    "            tailNode = rc(head.next, n - 2)\n",
    "            nextNode = head.next\n",
    "            head.next = tailNode\n",
    "            outTail = tailNode.next\n",
    "            tailNode.next = nextNode\n",
    "\n",
    "            return outTail\n",
    "\n",
    "        rc(head=head, n=N)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "\n",
    "class Solution:\n",
    "    def reorderList(self, head: ListNode) -> None:\n",
    "\n",
    "        \"\"\"\n",
    "        Do not return anything, modify head in-place instead.\n",
    "        \"\"\"\n",
    "\n",
    "        \"\"\"\n",
    "        Do not return anything, modify head in-place instead.\n",
    "        \"\"\"\n",
    "\n",
    "        if head is None or head.next is None or head.next.next is None:\n",
    "            return\n",
    "\n",
    "        N = 0\n",
    "        temp = head\n",
    "        while temp is not None:\n",
    "            N += 1\n",
    "            temp = temp.next\n",
    "\n",
    "        def rc(head: ListNode, n: int):\n",
    "\n",
    "            if n == 1:\n",
    "                tailNode = head.next\n",
    "                head.next = None\n",
    "                return tailNode\n",
    "\n",
    "            elif n == 2:\n",
    "                tailNode = head.next.next\n",
    "                head.next.next = None\n",
    "                return tailNode\n",
    "\n",
    "            tailNode = rc(head.next, n - 2)\n",
    "            nextNode = head.next\n",
    "            head.next = tailNode\n",
    "            outTail = tailNode.next\n",
    "            tailNode.next = nextNode\n",
    "\n",
    "            return outTail\n",
    "\n",
    "        rc(head=head, n=N)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reorderList(self, head: ListNode) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify head in-place instead.\n",
    "        \"\"\"\n",
    "        def reverse(head: ListNode) -> ListNode:\n",
    "            if not head or not head.next:\n",
    "                return head\n",
    "            new_head = reverse(head.next)\n",
    "            head.next.next = head\n",
    "            head.next = None\n",
    "            return new_head\n",
    "\n",
    "        fast = slow = head\n",
    "        pre = None\n",
    "        while fast and fast.next:\n",
    "            pre = slow\n",
    "            slow = slow.next\n",
    "            fast = fast.next.next\n",
    "        if not pre:\n",
    "            return\n",
    "        pre.next = None\n",
    "        curr = None\n",
    "        first = head\n",
    "        second = reverse(slow)\n",
    "        while first and second:\n",
    "            f = first\n",
    "            first = first.next\n",
    "            s = second\n",
    "            second = second.next\n",
    "            f.next = s\n",
    "            if not curr:\n",
    "                curr = f\n",
    "                curr = curr.next\n",
    "            else:\n",
    "                curr.next = f\n",
    "                curr = curr.next.next\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reverse(self,head):\n",
    "        if head is None or head.next is None:\n",
    "            return head\n",
    "        last = self.reverse(head.next)\n",
    "        head.next.next = head\n",
    "        head.next = None\n",
    "        return last\n",
    "\n",
    "    def mid(self,head):\n",
    "        fast = head\n",
    "        slow = head\n",
    "        while fast and fast.next:\n",
    "            fast = fast.next.next\n",
    "            slow = slow.next\n",
    "        return slow\n",
    "\n",
    "    def reorderList(self, head: ListNode) -> None:\n",
    "        p = head\n",
    "        q = self.mid(head)\n",
    "        q = self.reverse(q)\n",
    "        while q.next:\n",
    "            l1 = p.next\n",
    "            l2 = q.next\n",
    "            p.next = q\n",
    "            q.next = l1\n",
    "            p = l1\n",
    "            q = l2\n",
    "        return p\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reorderList(self, head: ListNode) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify head in-place instead.\n",
    "        \"\"\"\n",
    "        dummy = ListNode(0, head)\n",
    "        s, f = dummy, dummy\n",
    "        while f and f.next:\n",
    "            s = s.next\n",
    "            f = f.next.next\n",
    "        f = s.next\n",
    "        s.next = None       \n",
    "        def reverse(node):\n",
    "            if not node or not node.next:\n",
    "                return node\n",
    "            nex = node.next\n",
    "            new_head = reverse(node.next)\n",
    "            nex.next = node\n",
    "            node.next = None\n",
    "            return new_head\n",
    "        new_f = reverse(f)\n",
    "        cur = head\n",
    "        l1 = head.next\n",
    "        l2 = new_f\n",
    "        pre = True\n",
    "        while l1 or l2:\n",
    "            if pre:\n",
    "                cur.next = l2\n",
    "                l2 = l2.next\n",
    "                pre = False\n",
    "            else:\n",
    "                cur.next = l1\n",
    "                l1 = l1.next\n",
    "                pre = True\n",
    "            cur = cur.next\n",
    "        return s    \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reverse(self, node, pre):\n",
    "        if not node:\n",
    "            self.head = pre \n",
    "            return \n",
    "        self.reverse(node.next, node)\n",
    "        node.next = pre \n",
    "    def reorderList(self, head: ListNode) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify head in-place instead.\n",
    "        \"\"\"\n",
    "        \n",
    "        n = 0\n",
    "        p = head\n",
    "        while p:\n",
    "            p = p.next\n",
    "            n += 1\n",
    "        k = n+1 - (n//2)            # NOTE 倒数第 k 个\n",
    "        dummy = ListNode(-1)\n",
    "        dummy.next = head\n",
    "        fast, slow = dummy, dummy\n",
    "        for _ in range(k):\n",
    "            fast = fast.next\n",
    "        \n",
    "        while fast:\n",
    "            fast = fast.next\n",
    "            slow = slow.next\n",
    "\n",
    "        # 2. reverse \n",
    "        q = slow.next\n",
    "        slow.next = None \n",
    "        self.reverse(q, None)      \n",
    "        \n",
    "        # 3. \n",
    "        p, q = head, self.head\n",
    "        while q:\n",
    "            print(q.val)\n",
    "            q = q.next \n",
    "        q = self.head\n",
    "\n",
    "\n",
    "        while True:                                 # p 先到链尾    \n",
    "            if p and q:\n",
    "                a, b = p.next, q.next \n",
    "                p.next, q.next = q, p.next\n",
    "                p, q = a, b\n",
    "            else:\n",
    "                tail = head\n",
    "                while tail.next:\n",
    "                    tail = tail.next\n",
    "                tail.next = q\n",
    "                break "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
